package mine.code.question.动态规划;

import org.junit.Test;

/**
 * 输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 * <p>
 * 要求时间复杂度为O(n)。
 * <p>
 * 示例1:
 * <p>
 * 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出: 6
 * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 *
 * @author caijinnan
 * @date 2020/3/17 16:55
 */
public class 连续子数组的最大和 {

    @Test
    public void run() {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray(nums));
    }

    //如果数组有正有负,按顺序跳过数组为负数,开始累加的第一项必须是正数,如果累加之后为负数,则再从正数开始累加
    //如果只有负数,整个数组最大的负数
    public int maxSubArray(int[] nums) {
        //累加值
        int sum = nums[0];
        //记录正数开始后,每次相加后的最大值
        int resultNum = nums[0];
        for (int i = 1, length = nums.length; i < length; i++) {
            if (sum < 0) {
                sum = nums[i];
            } else {
                sum += nums[i];
            }
            resultNum = Math.max(resultNum, sum);
        }
        return resultNum;
    }
}